package com.chapter4.graph.mst;

import com.chapter1.basic.queue.Queue;
import com.chapter2.sort.IndexMinPQ;

/**
 * 
* @ClassName: EagerPrimMST 
* @Description: eager prim最小生成树 
* @author minjun
* @date 2015年3月9日 下午10:21:07 
*
 */
public class EagerPrimMST {

	private double weight;
	
	private Edge[] edgeTo;//edgeTo[w]表示从w节点（不在树中）到树的最小权重边
	
	private double[] distTo;//distTo[w]表示w节点(不在树中)到树的最小权重
	
	private boolean[] marked;//是否访问过该节点
	
	private IndexMinPQ<Double> pq;//带索引的优先队列
	
	private Queue<Edge> mst;//最小生成树

	public EagerPrimMST(WeightEdgeGraph g){
		int len=g.V();
		edgeTo=new Edge[len];
		pq=new IndexMinPQ<Double>(len);
		marked=new boolean[len];
		mst=new Queue<Edge>();
		distTo=new double[len];
		//初始化所有节点距离树的权重为一个极大值，作为之后进行较小比较的一个参考值
		for(int i=0;i<len;i++){
			distTo[i]=Double.POSITIVE_INFINITY;
		}
		distTo[0]=0;
		pq.insert(0, 0.0);
		while(!pq.isEmpty()){
			visit(g, pq.delMin());
		}
		
		for(Edge e:edgeTo){
			if(e!=null){
				mst.offer(e);
				weight+=e.weight();
			}
		}
	}
	
	private void visit(WeightEdgeGraph g,int v){
		marked[v]=true;
		for(Edge edge:g.adj(v)){
			int w=edge.other(v);
			if(!marked[w]){
				//如果该边的权重比数组中对应的权重大小要小，那么修改权重值为这个较小值
				double we=edge.weight();
				if(we<distTo[w]){
					distTo[w]=we;
					edgeTo[w]=edge;
					if(pq.contains(w)) 	pq.changeKey(w, we);
					else 				pq.insert(w, we);
				}
			}
		}
	}
	
	public Iterable<Edge> edges(){
		return mst;
	}
	
	public double weight(){
		return weight;
	}
	
}
